// 有一个信件投递员，每次都是从寄件箱里最上面取出一封信扫描地址后投递.
// 一个寄件人有5封信，分别用序号标记为1,2,3,4,5，寄件人按序号往寄件箱里放入信件。
// 给出5封信件的被投递出去的所有可能的顺序，输出顺序表达为1->2->3->4->5这样。

// 如只投递2封信的情况，可能顺序为
// 1 -> 2(放入第一封后立马被投递)
// 2 -> 1(放入第二封后才开始投递)


function dfs(stack, outBox, inBox, result) {
  // 终止条件：栈和待投列表都为空时，记录当前投递顺序
  if (stack.length === 0 && inBox.length === 0) {
    result.push(outBox.join('->'));
    return;
  }

  // 分支1：从栈顶取出信件投递（出栈操作）
  if (stack.length > 0) {
    const newStack = [...stack];  // 复制栈（避免修改原栈）
    const newOutBox = [...outBox];  // 复制已投递列表
    newOutBox.push(newStack.pop());  // 取出栈顶信件，加入已投递列表
    dfs(newStack, newOutBox, inBox, result);  // 递归搜索剩余可能
  }

  // 分支2：将待投列表的下一封信放入栈（入栈操作）
  if (inBox.length > 0) {
    const newStack = [...stack];  // 复制栈
    const newInBox = [...inBox];  // 复制待投列表
    newStack.push(newInBox.shift());  // 取出待投列表的第一封信（按顺序1→2→3→4→5），压入栈
    dfs(newStack, outBox, newInBox, result);  // 递归搜索剩余可能
  }
}

function allPossibleOrders(n) {
  // 第一个参数 { length: n } ：表示一个类数组对象，指定新数组的长度为 n （例如 n=5 时，数组长度为5）。
  // 第二个参数 (_, i) => i + 1 ：是一个映射函数，对每个元素进行处理。其中：
  // _ ：当前元素的值（由于类数组对象初始值为 undefined ，这里用 _ 表示不需要该值）。
  // i ：当前元素的索引（从0开始）。
  // i + 1 ：将索引转换为从1开始的数值（例如索引0对应1，索引1对应2，以此类推）。
  const inBox = Array.from({ length: n }, (_, i) => i + 1);
  const stack = [];
  const outBox = [];
  const result = [];
  dfs(stack, outBox, inBox, result);
  return result;
}

// 测试
const n = 5;
const orders = allPossibleOrders(n);
orders.forEach(order => console.log(order));